#include <iostream>
#include <ctime> 
#include <iostream>
#include <fstream>
using namespace std;  
template <class Data>
struct node {
    Data info;
    node *next;
	node()
	{
		next = NULL;
	}
};

template <class Data>
class Queue {
    private:
        node<Data> *front;
        node<Data> *end;
    public:
        Queue();
        ~Queue();
        bool isEmpty();
        void enqueue(Data);
        Data dequeue();
        void display(); 
 
}; 

template <class Data>
void Queue<Data>::display(){
    node<Data> *p = new node<Data>();
    p = front;
    if(front == NULL){
        cout<<"\nNothing to Display\n";
    }else{
        while(p!=NULL){
            cout<<endl<<p->info;
            p = p->next;
        }
    }
} 
 
template <class Data>
Queue<Data>::Queue() {
    front = NULL;
    end = NULL;
} 
 
template <class Data>
Queue<Data>::~Queue() {
    delete front;
} 
 
template <class Data>
void Queue<Data>::enqueue(Data data) {
    node<Data> *temp = new node<Data>();
    temp->info = data;
    temp->next = NULL;
    if(front == NULL){
        front = temp;
    }else{
        end->next = temp;
    }
    end = temp;
} 
 
template <class Data>
Data Queue<Data>::dequeue() {
    node<Data> *temp = new node<Data>();
    Data value;
    if(front == NULL){
        cout<<"\nQueue is Emtpty\n";
    }else{
        temp = front;
        value = temp->info;
        front = front->next;
        delete temp;
    }
    return value;
} 
 
template <class Data>
bool Queue<Data>::isEmpty() {
    return (front == NULL);
}

struct nodePath{
	int edge;
	int weight;
	nodePath(int e,int w){
		edge = e;
		weight = w;
	};
	nodePath()
	{
		edge = 0;
		weight = 0;
	}
};
 
class Graph {
    private:
        int n;
        int **A;
		void createGraph(int size = 2);
    public:
        Graph(int size = 2);
		Graph(char fname[100]);
        ~Graph();
        bool isConnected(int, int);
		int connectionWeight(int, int);
		int numberOfAllEdgesWithEvenPath(int);
        void addEdge(int x, int y, int w);
        void BFS(int , int);
}; 
 
Graph::Graph(char fname[100])
{
	fstream ifile;
	ifile.open(fname,ios::in);
	int n;
	ifile>>n;
	createGraph(n);
	int start,end,weight;
	while (!ifile.eof())
	{
		ifile>>start>>end>>weight;
		addEdge(start,end,weight);
	}
	ifile.close();
}

Graph::Graph(int size) {
    createGraph(size);
}

void Graph::createGraph(int size)
{
	int i, j;
    if (size < 2) n = 2;
    else n = size;
    A = new int*[n];
    for (i = 0; i < n; ++i)
        A[i] = new int[n];
    for (i = 0; i < n; ++i)
        for (j = 0; j < n; ++j)
            A[i][j] = 0;
}
 
Graph::~Graph() {
    for (int i = 0; i < n; ++i)
    delete [] A[i];
    delete [] A;
} 

bool Graph::isConnected(int x, int y){
	return A[x-1][y-1] != 0;
}

int Graph::connectionWeight(int x, int y) {
    return (A[x-1][y-1]);
} 
 
void Graph::addEdge(int x, int y, int w) {
    A[x-1][y-1] = A[y-1][x-1] = w;
} 
 
void Graph::BFS(int x, int required) {
    Queue<int> Q;
    bool *visited = new bool[n+1];
    int i;
    for (i = 1; i <= n; ++i)
    visited[i] = false;
    Q.enqueue(x);
    if(x == required) return;
    visited[x] = true;
    cout << "Breadth first Search starting from vertex ";
    cout << x << " : " << endl;
    while (!Q.isEmpty()) {
        int k = Q.dequeue();
        if(k == required){
            cout<<" FOUND HERE ";
            continue;
        }
        cout << k << " ";
        for (i = 1; i <= n; ++i)
            if (isConnected(k, i) && !visited[i]) {
                Q.enqueue(i);
                visited[i] = true;
            }
    }
    cout << endl;
    delete [] visited;
}

int Graph::numberOfAllEdgesWithEvenPath(int start)
{
	int evenEdges = 0;
	Queue<nodePath> Q;
	bool** visitedPath;

	bool *countedEdge = new bool[n+1];

	visitedPath = new bool*[n+1];
    for (int i = 0; i < n+1; ++i)
        visitedPath[i] = new bool[n+1];
    for (int i = 0; i < n+1; ++i)
        for (int j = 0; j < n+1; ++j)
		{
            visitedPath[i][j] = false;
			countedEdge[j] = false;
		}

	countedEdge[start] = true;
	nodePath p(start, 0);
	Q.enqueue(p);
	while (!Q.isEmpty()) {
		nodePath pPrev = Q.dequeue();
		int edge = pPrev.edge;
		int weight = pPrev.weight;
		
		if ( !countedEdge[edge] && weight % 2 == 0)
		{
			evenEdges ++;
		}
		for (int i = 1; i <= n; ++i)
		{
			if (i != start)
			{
				if (isConnected(edge, i) && !visitedPath[edge][i]) {
					nodePath pNext(i, weight + connectionWeight(edge, i));
					Q.enqueue(pNext);
					visitedPath[edge][i] = true;
					visitedPath[i][edge] = true;
				}
			}
		}
	}
	return evenEdges;
}

int main()
{
	Graph graph("input.txt");
	cout<<graph.numberOfAllEdgesWithEvenPath(1)<<endl;
}